#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int HeapDataType;
typedef struct Heap {
	HeapDataType* a;
	int size;
	int capacity;
}Heap;
void adjustdown(HeapDataType*a,int i,int n) {
	assert(a);
	int j = 2 * i + 1;
	if (a[j] < a[j + 1]&&j<n-1) {
		j++;
	}
	if (a[i] < a[j]&&j<n) {
		HeapDataType x = a[i];
		a[i] = a[j];
		a[j] = x;
		adjustdown(a, j, n);
	}
}
HeapDataType* HeapCreate(HeapDataType*a,int n) {
	assert(a);
	HeapDataType* tmp = (HeapDataType*)malloc(n * sizeof(HeapDataType));
	if (tmp == NULL) {
		perror("HeapCreate:malloc");
		exit(1);
	}
	for (int i = 0; i < n; i++) {
		tmp[i] = a[i];
	}
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		adjustdown(tmp, i, n);
	}
	return tmp;
}
void HeapSort(HeapDataType* a, int n) {
	assert(a);
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		adjustdown(a, i, n);
	}
	while (n) {
		HeapDataType x = a[0];
		a[0] = a[n-1];
		a[n-1] = x;
		n--;
		adjustdown(a, 0, n);
	}
}
void HeapDestory(HeapDataType*a) {
	assert(a);
	free(a);
}
int main()
{
	int a[10] = { 0,5,12,6,8,2,4,14,3,16 };

	HeapSort(a, 10);
	for (int i = 0; i < 10; i++) {
		printf("%d ", a[i]);
	}
}